package com.lsa.letcode.the39.combinationSum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	List<List<Integer>> sols = new ArrayList<>();
    	
    	if (target != 0) {
    		Arrays.sort(candidates);
    		candidates = uniq(candidates);
    		
    		int[] state = new int[candidates.length];
    		combine(0, candidates, state, target, sols);
    	}
    	
    	return sols;
    }
    
    private int[] uniq(int[] arr) {
    	List<Integer> l = new ArrayList<>(arr.length);
    	int prev = -1;
    	for (int i = 0; i < arr.length; i++) {
			if (arr[i] != prev) {
				l.add(arr[i]);
				prev = arr[i];
			}
		}
    	
    	int[] res = new int[l.size()];
    	for (int i = 0; i < l.size(); i++) {
			res[i] = l.get(i);
		}    	
    	return res;
    }
    
    @SuppressWarnings("unused")
	private void printState(int i, int[] candidates, int[] use, int target, List<List<Integer>> sols, boolean isSol) {
    	for (int j = 0; j < use.length; j++) {
			System.out.print(String.format("%s ", use[j]));
		}
    	System.out.print(","+i);
    	System.out.println(isSol? "*" : "");
    }
    
    private void combine(int i, int[] candidates, int[] use, int target, List<List<Integer>> sols) {
    	@SuppressWarnings("unused")
		boolean isSol = false;
    	if (i == candidates.length || target < 0) {
    		return;
    	}
    	else if (target == 0) {
    		List<Integer> sol = new ArrayList<Integer>();
    		for (int j = 0; j < use.length; j++) {
    			for (int k = 0; k < use[j]; k++) {
    				sol.add(candidates[j]);
				}
			}
    		sols.add(sol);
    		isSol = true;
    	}
    	else {
    		// take
    		use[i]++;
    		combine(i, candidates, use, target - candidates[i], sols);
    		
    		//not take
    		use[i]--;
    		combine(i + 1, candidates, use, target, sols);
    	}
//    	printState(i, candidates, use, target, sols, isSol);
    }
}